#include<stdio.h> 
#include<stdlib.h>

# define Guimo 18
# define Total_step Guimo*Guimo // 马的总步数
# define Row     Guimo          // 棋盘的行数
# define Columns Guimo          // 棋盘的列数
# define Drections 8            // 每一步的八个方向
# define x_0 9                  // 初始位置横坐标
# define y_0 9                  // 初始位置纵坐标
# define jilu 0                 // 是否记录回溯次数，选择会拖慢程序执行时间
# define huanyou 1              // 设置是否要求哈密顿解，哈密顿求解规模小于12时一分钟内出结果；仅走完全盘则最大规模可达60


const int* par = 0;     // 用于排序的常量
int times = 0;          // 记录走完全盘的次数
int deta_x[Drections] =     { 1,2,2,1,-1,-2,-2,-1 };
int deta_y[Drections] = { 2,1,-1,-2,-2,-1,1,2 };           // 八个方向，优先顺序将极大的影响遍历效果
int sorted[Drections] = { 0,1,2,3,4,5,6,7 };                   // 基于贪心算法对上述八个顺序进行动态调整的排序索引
int qipan[Row][Columns];                                 // 二维数组棋盘
void print_result();                                     // 打印棋盘的函数
int  check(int x_new, int y_new);                        // 对马的下一步进行检验，是否在棋盘内并且未被遍历过
int  Find(int x, int y, int deep);                       // 主递归函数
void sort_direction(int x, int y);                       // 对八个方向进行排序的函数
int  compare(const void* p1, const void* p2);            // 快速排序的比较函数
void sort_index(const int ar[], int index[], int num);   // 依据sort_direction 得到的方向权值给索引排序的函数

int main() {
	// 初始化棋盘
	for (int i = 0; i < Row; i++)
		for (int j = 0; j < Columns; j++)
			qipan[i][j] = 0;
	// 输出终端界面
	printf("-----------------------------------------------------\n");
	printf("--------------------马踏棋盘问题---------------------\n");
	printf("----------------------------------刘方程：16070199012\n\n");
	// 初始化起点
	qipan[x_0 - 1][y_0 - 1] = 1;
	// 是否找到路径 
	if (Find(x_0 - 1, y_0 - 1, 2) == 1)
		printf("\n递归成功!\n");
	else
		printf("\n递归失败!\n");
	return 1;
}
// print()函数进行输出结果  
void print_result()
{
	printf("\n");
	int i, j;
	for (i = 0; i < Row; i++) {
		for (j = 0; j < Columns; j++)
			printf("%4d", qipan[i][j]);
		printf("\n");
	}
}
// Check()函数检查新产生的点是否满足条件，满足则返回1.
int check(int x_new, int y_new)
{
	if (x_new >= 0 && x_new < Row && y_new >= 0 && y_new < Columns && qipan[x_new][y_new] == 0)
		return 1;
	return 0;
}
// deep为递归的深度,当深度达到 Total_step=64 时表示遍历结束
int Find(int x, int y, int deep)
{
	if (x_0 == 1 && y_0 == 1) {
		if (deep <= Total_step - 1)
			qipan[2][1] = 1;
		else 		qipan[2][1] = 0;
	}
	if (x_0 == 1 && y_0 == Columns) {
		if (deep <= Total_step - 1)
			qipan[2][Columns-2] = 1;
		else  qipan[2][Columns - 2] = 0;
	}
	if (x_0 == Row && y_0 == Columns) {
		if (deep <= Total_step - 1)
			qipan[Row-3][Columns - 2] = 1;
		else  qipan[Row - 3][Columns - 2] = 0;
	}
	if (x_0 == Row && y_0 == 1) {
		if (deep <= Total_step - 1)
			qipan[Row - 2][2] = 1;
		else  qipan[Row - 2][ 2] = 0;
	}
	int i, x_new, y_new;
	sort_direction(x, y);                   // 对八个方向进行排序
	for (i = 0; i < Drections; i++) {
		x_new = x + deta_x[sorted[i]];      // 按照排序后的方向进行搜索
		y_new = y + deta_y[sorted[i]];
		int detax = abs(x_new - x_0 + 1);
		int detay = abs(y_new - y_0 + 1);
		if (check(x_new, y_new) == 1)       // 检查点a[xx][yy]是否满足条件  
		{
			qipan[x_new][y_new] = deep;
			if (jilu == 1) {
			if (deep == Total_step)         // 用于记录找到最优解经历了多少次达到深度最大值的回溯次数
				printf("第%3d 次走完全盘\n", ++times);
			}
			// 最优解终止条件
			if (huanyou == 1) {
				if (deep >= Total_step && (detax*detax + detay*detay == 5)) {
					print_result();
					return 1;
				}
			}
			else {
				if (deep == Total_step) {
					print_result();
					return 1;
				}
			}
		
			if (Find(x_new, y_new, deep + 1) == 1)  // 如果返回的是1，表示遍历完成。  
				return 1;
			else                                    // 如果返回的不是1，表示遍历未完成，继续搜索。  
				qipan[x_new][y_new] = 0;            // 一定要通过此步骤将棋盘还原
		}
	}
	return 0;
}
// 对八个方向排序
void  sort_direction(int x, int y) {
	int x_new, y_new, xx_new, yy_new;
	int score[Drections] = { 8,8,8,8,8,8,8,8};           // 定义不同方向的得分权值
	for (int i = 0; i < Drections; i++) {
		int count = 0;
		x_new = x + deta_x[i];
		y_new = y + deta_y[i];
		if (check(x_new, y_new) == 1) {           // 检查点a[xx][yy]是否满足条件  
			for (int j = 0; j < Drections; j++) {
				xx_new = x_new + deta_x[j];
				yy_new = y_new + deta_y[j];
				if (check(xx_new, yy_new) == 1)   // 检查点a[xx][yy]是否满足条件  
					count++;
			}
		}
		score[i] = count;
	}
	sort_index(score, sorted, Drections);                 // 快速排序
}
int compare(const void* p1, const void* p2)
{
	int a = *(int*)p1;
	int b = *(int*)p2;
	if (par[a] > par[b])
		return 1;
	else if (par[a] == par[b])
		return 0;
	else
		return -1;
}

void sort_index(const int ar[], int index[], int num)
{
	par = ar;
	qsort(index, num, sizeof(int), &compare);
}
